package com.xcc.dataStructures.demo14_algapplication;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 马踏棋盘(骑士周游)
 */
public class Demo10_HorseChessboard {

    public static void main(String[] args) {
        ChessBoard chessBoard = new ChessBoard(8, 8);
        System.out.println("开始运行骑士周游算法:");
        long start = System.currentTimeMillis();
        chessBoard.start(0, 0, 1);
        long end = System.currentTimeMillis();
        System.out.println("耗时: " + (end - start) + " ms");
        chessBoard.show();
    }

}

class ChessBoard {
    //原始棋盘
    private int[][] chess;
    //棋盘的总行
    private int X;
    //棋盘的列
    private int Y;
    //标记是否被访问
    private boolean[] visited;
    //标识棋盘是否走完
    private boolean finished;

    public ChessBoard(int X, int Y) {
        this.X = X;
        this.Y = Y;
        chess = new int[X][Y];
        visited = new boolean[X * Y];
    }

    /**
     * 马踏棋盘算法核心
     *
     * @param x    初始棋子在棋盘的哪一行
     * @param y    初始棋子在棋盘的哪一列
     * @param step 当前是第几步
     */
    public void start(int x, int y, int step) {
        //首先存储对应的步数
        chess[x][y] = step;
        //获取当前x,y对应的 visited数组中的索引位置
        int index = x * Y + y;
        //标记为已访问
        visited[index] = true;
        //构建当前point
        Point currentPoint = new Point(x, y);
        List<Point> ps = next(currentPoint);
        //对ps进行排序,排序的规则就是对ps的所有的Point对象的下一步的位置的数目，进行非递减排序
        sort(ps);
        while (!ps.isEmpty()) {
            //将第一个元素移除
            Point removePoint = ps.remove(0);
            //未被访问过，则调用当前
            if (!visited[(removePoint.x) * Y + removePoint.y]) {
                start(removePoint.x, removePoint.y, step + 1);
            }
        }

        //回溯
        if (step < X * Y && !finished) {
            chess[x][y] = 0;
            visited[index] = false;
        } else {
            finished = true;
        }

    }

    /**
     * 对ps集合进行非递减排序
     * @param ps    集合
     */
    private void sort(List<Point> ps) {
        ps.sort((p1, p2) -> {
            //获取当前p1和p2  各自对应的
            List<Point> next1 = next(p1);
            List<Point> next2 = next(p2);
            return next1.size() - next2.size();
        });
    }

    private List<Point> next(Point currentPoint) {
        List<Point> ps = new ArrayList<>();
        int x, y;
        //0
        if ((x = currentPoint.x - 1) >= 0 && (y = currentPoint.y + 2) < Y) {
            ps.add(new Point(x, y));
        }
        //1
        if ((x = currentPoint.x + 1) < X && (y = currentPoint.y + 2) < Y) {
            ps.add(new Point(x, y));
        }
        //2
        if ((x = currentPoint.x + 2) < X && (y = currentPoint.y + 1) < Y) {
            ps.add(new Point(x, y));
        }
        //3
        if ((x = currentPoint.x + 2) < X && (y = currentPoint.y - 1) >= 0) {
            ps.add(new Point(x, y));
        }
        //4
        if ((x = currentPoint.x + 1) < X && (y = currentPoint.y - 2) >= 0) {
            ps.add(new Point(x, y));
        }
        //5
        if ((x = currentPoint.x - 1) >= 0 && (y = currentPoint.y - 2) >= 0) {
            ps.add(new Point(x, y));
        }
        //6
        if ((x = currentPoint.x - 2) >= 0 && (y = currentPoint.y - 1) >= 0) {
            ps.add(new Point(x, y));
        }
        //7
        if ((x = currentPoint.x - 2) >= 0 && (y = currentPoint.y + 1) < Y) {
            ps.add(new Point(x, y));
        }
        return ps;
    }

    public void show() {
        for (int i = 0; i < X; i++) {
            for (int j = 0; j < Y; j++) {
                System.out.printf("%d\t", chess[i][j]);
            }
            System.out.println();
        }
    }
}
